1. Field of the Invention
The present invention relates to data and telecommunications networks, and, in particular, to the processing of data packets in such networks.
2. Description of the Related Art
The growing need to satisfy diverse networking requirements, such as application-dependent packet handling, customer-specific policy-based routing, disruption-free new protocol deployment, etc., has led to increased interest in building virtual network infrastructures that can satisfy these diverse needs, while sharing a common physical network for cost efficiency. Deploying these virtual network infrastructures involves the use of virtual routers that act as stand-alone routers despite sharing a common physical platform with other virtual routers. An ideal virtualization goal is to achieve good isolation amongst the virtual routers, while also achieving high scaling in the sense that a large number of virtual routers can concurrently run on the same physical platform. However, these two goals of isolation and scaling typically have conflicting system needs. Isolation sets limits on the sharing of scarce physical router resources, whereas scaling requires that scarce resources be efficiently shared.
Another example of the need for differing routing functions on the same platform, akin to virtualization, is the case of IPv4-to-IPv6 migration. Since an overnight conversion to IPv6 will not happen and any migration will be slow, routers have to support both IPv4 and IPv6 routing simultaneously. In each such router, packets are classified based on the IP version and then forwarded using the corresponding forwarding tables. This is similar to having two virtual routers on the same platform.
Another example of the need for differing routing functions on the same platform is for the case of Layer 3 MPLS Virtual Private Networks (L3 VPNs). L3 VPNs allow enterprises to securely achieve any-to-any reachability amongst all their sites while outsourcing their routing needs to the service provider. The service provider's edge router, which performs the routing for each VPN customer, needs to simultaneously handle a large number of VPNs and needs to maintain a private routing table for each VPN customer. With the rapid growth in the VPN market, the memory required for storing VPN routing tables has become a critical resource and a key bottleneck in provisioning new customers.
As virtual network infrastructures become more and more popular, a physical router will be expected to support a few tens and possibly even hundreds of virtual routers with each having its own forwarding table and routing protocol instances. For example, Juniper routers from Juniper Networks, Inc., of Sunnyvale, Calif., are currently reported to be capable of supporting up to 16 virtual routers. Scaling to these numbers poses a challenging problem, especially if complex packet classification and deep-packet inspection functions need to be performed by the virtual routers.
A critical resource that limits scaling is the limited amount of high-speed memory available for caching the packet forwarding and filtering data structures. It is straightforward to partition the available memory and allocate a fraction to each virtual router. This simple partitioning has the benefit of isolating the memory usage of the virtual routers. However, it is not memory efficient and severely limits scalability for the following reasons.
First, it is difficult to determine the right fractions to allocate to each virtual router when each virtual router has different forwarding-table sizes that change dynamically. Consider the IPv4-to-IPv6 migration example. Currently, the IPv6 forwarding table is small (e.g., a few thousand prefixes), and the IPv4 forwarding table is large (e.g., a few tens of thousands to hundreds of thousands prefixes). Clearly, these sizes will change over the time. Both tables may continue to grow for a while. Ultimately, it is possible that the IPv4 table may actually shrink if large numbers of IPv4-capable hosts migrate to IPv6. The virtual router dynamics make static provisioning inflexible and inefficient.
Second, the overall memory consumption is linear in the number of virtual routers as well as in the size of the memory required for each virtual router. For example, forwarding tables are typically stored in static random access memories (SRAMs) or ternary content-addressable memories (TCAMs), which account for a large portion of the system cost and power dissipation. An 18 Mb TCAM can store 500K IPv4 (or 250K IPv6) prefixes. This is hardly sufficient for two unique Border Gateway Protocol (BGP) tables, which already contain about 300K prefixes. When algorithmic solutions for longest-prefix matches are used, just 10 moderate-sized forwarding tables, stored separately, use up to 120 Mb of SRAM. Scaling to larger numbers makes the memory requirements prohibitive. Static partitioning of the available memory with each router maintaining independent data structures, though desirable for isolation, imposes a severe constraint on scaling.